package com.mzy.interview

import java.util.LinkedList

/**
 * @Author: mizy3
 * @Date: 2024/08/24/下午4:12
 * @Description:
 */
class Ks二面字母组合 {

    fun permute(str: String): MutableList<String> {
        val ans = mutableListOf<String>()
        val path = LinkedList<Char>();
        val used = BooleanArray(str.length)

        backtracking(str, 0, path, used, ans);

        return ans;
    }

    private fun backtracking(
        str: String,
        depth: Int,
        path: LinkedList<Char>,
        used: BooleanArray,
        ans: MutableList<String>
    ) {
        if (depth == str.length) {
            val builder = StringBuilder()
            path.forEach(builder::append)
            ans.add(builder.toString())
            return;
        }

        for (i in 0 ..< 3) {
            if(used[i] || i > 0 && str[i] == str[i - 1] && used[i - 1]){
                continue;
            }
            used[i] = true
            path.addLast(str[i])
            backtracking(str, depth + 1, path, used, ans)
            path.removeLast()
            used[i] = false
        }
    }


}

fun main(args: Array<String>) {
    // abc [abc, acb, bac, bca, cab, cba]
    // abb [abb, bab, bba]
    // 回溯
    println(Ks二面字母组合().permute("abb"))
}